package com.mdnote.practice.dfs_bfs;

import javax.naming.LinkLoopException;
import java.awt.*;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/17
 * @description  扫雷游戏
 */
public class LeetCode529 {

    private static int[] dx = { 0, -1, -1, -1,  0,  1,  1,  1};
    private static int[] dy = {-1, -1,  0,  1,  1,  1,  0, -1};

    public static void main(String[] args) {
        LeetCode529 leetCode529 = new LeetCode529();

        char[][] chars = {
                {'E', 'E', 'E', 'E', 'E'},
                {'E', 'E', 'M', 'E', 'E'},
                {'E', 'E', 'E', 'E', 'E'},
                {'E', 'E', 'E', 'E', 'E'}
        };

        leetCode529.updateBoard(chars, new int[]{3, 0});
    }

    public char[][] updateBoard(char[][] board, int[] click) {
        if (board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
        }
        // solution by DFS
//        dfs(board, click);

        // BFS
        bfs(board, click);
        for (char[] chars : board) {
            System.out.println(Arrays.toString(chars));
        }
        return board;
    }

    private void bfs(char[][] board, int[] click) {
        LinkedList<Point> queue = new LinkedList<>();
        queue.add(new Point(click[1], click[0]));

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point point = queue.removeFirst();

                int count = check(board, point.x, point.y);
                if (count == 0) {
                    board[point.y][point.x] = 'B';
                    for (int j = 0; j < dx.length; j++) {
                        if (point.y + dy[j] >= 0 && point.y + dy[j] < board.length &&  point.x + dx[j] >= 0 && point.x + dx[j] < board[0].length) {
                            if (board[point.y + dy[j]][point.x + dx[j]] == 'E'){
                                queue.addLast(new Point(point.x + dx[j], point.y + dy[j]));
                            }
                        }
                    }
                } else {
                    board[point.y][point.x] = (char)(48 + count);
                }
            }
        }
    }

    private void dfs(char[][] board, int[] click) {
        // Terminator
        if (board[click[0]][click[1]] != 'E') {
            return;
        }

        // process
        int count = check(board, click[1], click[0]);
        if (count == 0) {
            board[click[0]][click[1]] = 'B';
            // 继续递归
            for (int i = 0; i < dx.length; i++) {
                if (click[0] + dy[i] >= 0 && click[0] + dy[i] < board.length &&  click[1] + dx[i] >= 0 && click[1] + dx[i] < board[0].length) {
                    dfs(board, new int[]{click[0] + dy[i], click[1] + dx[i]});
                }
            }
        } else {
            board[click[0]][click[1]] = (char)(48 + count);
        }
    }

    /**
     * 计算周围的炸弹个数
     * @param board 地图
     * @param x 横坐标
     * @param y 纵坐标
     * @return 炸弹个数
     */
    private int check(char[][] board, int x, int y) {
        int count = 0;
        for (int i = 0; i < dx.length; i++) {
            // 判断是否越界，board[y][x]
            if (x + dx[i] >= 0 && x + dx[i] < board[0].length && y + dy[i] >= 0 && y + dy[i] < board.length) {
                if (board[y + dy[i]][x + dx[i]] == 'M') {
                    count++;
                }
            }
        }
        return count;
    }
}
